\input{../preambules/preDM.tex}
\usepackage{listings}
\usetikzlibrary{shapes}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Pro}{\text{P}}
\def\ccl#1{\[ \boxed{#1}\]}
\begin{document}

\chead{Correction SIGMA n°2B}
\lfoot{}
\cfoot{}

\begin{center}
\fbox{ \Large Correction SIGMA n°2B}
\end{center}
\vspace{30pt}

\section*{Exercice 1 - Inspiré EDHEC 1995}
\begin{enumerate}
\item A l'instant 0, le mobile est en $O$ donc \begin{center}
\fbox{$P(E_{0,0})=1$ et $P(E_{0,-1})=P(E_{0,1})=0$.}
\end{center}
Puisqu'à l'instant 0 le mobile est en $O$, il sera en $A$ avec probabilité $p$ et en $B$ avec probabilité $q$, c'est à dire
\begin{center}
\fbox{$P(E_{1,0})=0,~ P(E_{1,1})=p \text{ et } P(E_{1,-1})=q$}
\end{center}
\item \begin{enumerate}
\item Le mobile ne reste pas sur place entre deux instants successifs donc pour tout $i\in\{-1,0,1\}$, 
\begin{center}
\fbox{$P_{E_{n,i}}(E_{n+1,i})=0$.}
\end{center}
Si le mobile est en $O$ à l'instant $n$, il sera à l'instant $n+1$ en $A$ avec probabilité $p$ et en $B$ avec probabilité $q$ donc 
\begin{center}
\fbox{$P_{E_{n,0}}(E_{n+1,1})=p$ et $P_{E_{n,0}}(E_{n+1,-1})=q$.}
\end{center}
Si le mobile est en $A$ ou en $B$ alors à l'instant $n+1$ il retourne en $O$ donc 
\begin{center}
\fbox{$P_{E_{n,1}}(E_{n+1,0})=P_{E_{n,-1}}(E_{n+1,0})=1$ et $P_{E_{n,1}}(E_{n+1,-1})=P_{E_{n,-1}}(E_{n+1,1})=0$.}
\end{center}
\item Soit $n\in\N$, alors $\{E_{n,-1},E_{n,0},E_{n,1}\}$ est un système complet d'événements finis. On a donc d'après la formule des probabilités totales, pour tout $i\in\{-1,0,1\}$,
$$P(E_{n+1,i})=P_{E_{n,-1}}(E_{n+1,i})P(E_{n,-1})+P_{E_{n,0}}(E_{n+1,i})P(E_{n,0})+P_{E_{n,1}}(E_{n+1,i})P(E_{n,1}).$$
En utilisant les résultats de la question (2)(a) on obtient
\begin{center}
\fbox{$\Pro(E_{n+1,-1})=q\Pro(E_{n,0}),~
\Pro(E_{n+1,0})=\Pro(E_{n,-1})+\Pro(E_{n,1}) \text{ et }
\Pro(E_{n+1,1})=p\Pro(E_{n,0}).$}
\end{center}
\end{enumerate}
\item \begin{enumerate}
\item Le résultat de la question (2)(b) peut s'écrire
$$\begin{pmatrix}\Pro(E_{n+1,-1})\\\Pro(E_{n+1,0})\\\Pro(E_{n+1,1}) \end{pmatrix}=\begin{pmatrix}0 & q & 0\\1 & 0 & 1\\ 0 & p & 0 \end{pmatrix} \begin{pmatrix}\Pro(E_{n,-1})\\\Pro(E_{n,0})\\\Pro(E_{n,1}) \end{pmatrix}.$$
Autrement dit, \begin{center}
\fbox{$U_{n+1}=MU_n$ avec 
$M=\begin{pmatrix}0 & q & 0\\1 & 0 & 1\\ 0 & p & 0 \end{pmatrix}.$}
\end{center}
\item Montrons par récurrence sur $n$ que, pour tout $n\in\N$, $U_n=M^nU_0$.\\
Pour $n=0$ on a bien $M^0U_0=I_3U_0=U_0$.\\
Soit $n\in\N$, supposons que $U_n=M^nU_0$. Alors on a $U_{n+1}=MU_n=MM^nU_0=M^{n+1}U_0$. Donc l'égalité reste vraie au rang $n+1$.\\
\begin{center}
\fbox{On a donc, pour tout $n\in\N$, $U_n=M^nU_0$.}
\end{center}
\item Le script Scilab est 
\begin{verbatim}
n = input("Entrez n: ")
p = input("Entrez p: ")
q = input("Entrez q: ")

M = [0, q , 0 ; 1, 0, 1 ; 0, p, 0]
U0 = [0; 1; 0]
U = M^n*U0
disp(U)
\end{verbatim}
\end{enumerate}
\item \begin{enumerate}
\item Pour montrer que $Q$ est inversible il suffit de résoudre le système linéaire suivant
\begin{align*}
\begin{cases} qx_1+x_2+qx_3&=y_1\\-x_1\hspace{22pt}+x_3&=y_2\\ px_1-x_2+px_3&=y_3\end{cases}&\Longleftrightarrow \begin{cases} \phantom{q}x_1\hspace{22pt}+qx_3&=y_1+y_3 \hspace{40pt} L_1\leftarrow L_1+L_3\\-x_1\hspace{22pt}+x_3&=y_2\\ px_1-x_2+px_3&=y_3\end{cases}\\
&\Longleftrightarrow \begin{cases} \phantom{q}x_1\hspace{22pt}+qx_3&=y_1+y_3\\\phantom{-x_1}\hspace{32pt}2x_3&=y_1+y_2+y_3\hspace{20pt} L_2\leftarrow L_2+L_1\\ \phantom{px_1}-x_2\phantom{+px_3}&=-py_1+qy_3\hspace{23pt}L_3\leftarrow L_3-pL_1\end{cases}\\
&\Longleftrightarrow \begin{cases}x_1&=\frac12(y_1-y_2+y_3)\\x_2&=py_1-qy_3\\x_3&=\frac12(y_1+y_2+y_3)\end{cases}\\
\end{align*}
Donc $Q$ est inversible et $Q^{-1}=\ds\frac12\begin{pmatrix}1&-1&1\\2p&0&-2q\\1&1&1 \end{pmatrix}$.
\remarque{Vous pouvez également utiliser la méthode du cours pour trouver $Q^{-1}$}
\item Calculons $QDQ^{-1}$.
\begin{align*}
QDQ^{-1} &= \frac12\begin{pmatrix}q&1&q\\-1&0&1\\p&-1&p \end{pmatrix}\begin{pmatrix}-1 & 0&0\\0&0&0\\0&0&1\end{pmatrix}\begin{pmatrix}1&-1&1\\2p&0&-2q\\1&1&1 \end{pmatrix}\\
&= \frac12\begin{pmatrix}q&1&q\\-1&0&1\\p&-1&p \end{pmatrix}\begin{pmatrix}-1&1&-1\\0&0&0\\1&1&1\end{pmatrix}=\begin{pmatrix}0 & q & 0\\1 & 0 & 1\\ 0 & p & 0 \end{pmatrix}=M
\end{align*}
\begin{center}
\fbox{On a donc bien $QDQ^{-1}=M$.}
\end{center}
\item Montrons par récurrence sur $n$ que, pour tout $n\in\N$, $M^n=QD^nQ^{-1}$.\\
Pour $n=0$ on a bien $QD^0Q^{-1}=QI_3Q^{-1}=QQ^{-1}=I_3=M^0$.\\
Soit $n\in\N$, supposons que $M^n=QD^nQ^{-1}$, alors
$$M^{n+1}=M^nM=QD^nQ^{-1}QDQ^{-1}=QD^nDQ^{-1}=QD^{n+1}Q^{-1}$$
L'égalité reste donc vraie au rang $n+1$ et donc on a obtenu que \begin{center}
\fbox{pour tout $n\in\N$, $M^n=QD^nQ^{-1}$.}
\end{center}
\end{enumerate}
\item \begin{enumerate}
\item Tout d'abord, on sait d'après le cours que, pour tout $n\in\N$, $$D^n=\begin{pmatrix}(-1)^n & 0&0\\0&0&0\\0&0&1\end{pmatrix}.$$\\
Soit $n\in\N$, calculons $U_n$. 
\begin{align*}
U_n&=M^nU_0=QD^nQ^{-1}U_0 =  \frac12\begin{pmatrix}q&1&q\\-1&0&1\\p&-1&p \end{pmatrix}\begin{pmatrix}(-1)^n & 0&0\\0&0&0\\0&0&1\end{pmatrix}\begin{pmatrix}1&-1&1\\2p&0&-2q\\1&1&1 \end{pmatrix}\begin{pmatrix}0\\1\\0 \end{pmatrix}\\
&=\frac12\begin{pmatrix}(-1)^nq & 0 & q\\(-1)^{n+1} & 0 & 1\\ (-1)^np&0&p \end{pmatrix} \begin{pmatrix}-1\\0\\1 \end{pmatrix} =\frac12 \begin{pmatrix}(-1)^{n+1}q+q\\(-1)^n+1\\(-1)^{n+1}p+p \end{pmatrix}
\end{align*}
On a donc, pour tout $n\in\N$,
\begin{center}
\fbox{$P(E_{n,-1})=\frac q2\left((-1)^{n+1}+1\right),~P(E_{n,0})=\frac12\left((-1)^n+1\right)\text{ et } P(E_{n,1})=\frac p2\left((-1)^{n+1}+1\right)$}
\end{center}
\item On a en particulier $P(E_{2n,0})=\frac12\left((-1)^{2n}+1\right)=1$. On aurait pu prévoir ce résultat car à l'instant 0 le mobile est en $O$, à l'instant 1 en $A$ ou $B$, à l'instant 2 le mobile revient en $O$, etc...\\
Ainsi, à tout instant pair, le mobile est en $O$ et donc \begin{center}
\fbox{pour tout $n\in\N$, l'événement $E_{2n,0}$ est certain.}
\end{center}
\end{enumerate}
\end{enumerate}

\section*{Exercice 2}
Soit $a$ et $b$ des réels avec $0<a<b$. Soit $(u_n)_{n\in\N}$ et $(v_n)_{n\in\N}$ deux suites définies par $u_0=a$, $v_0=b$ et, pour tout $n\in\N$,
\vspace{-5pt}$$u_{n+1}=\frac{u_n^2}{u_n+v_n}\text{ et }v_{n+1}=\frac{v_n^2}{u_n+v_n}.$$
\begin{enumerate}
\item Montrons par récurrence sur $n$ que
$$\forall n\in\N,~u_n\text{ et } v_n\text{ existent bien et } u_n>0,~v_n>0.$$
Tout d'abord, on a bien $u_0=a>0$ et $v_0=b>0$.\\
Soit $n\in\N$, supposons que $u_n$ et $v_n$ existent bien et que $u_n>0$ et $v_n>0$.\\
On a alors $u_n+v_n>0$ donc, en particulier, $u_n+v_n\neq0$ et ainsi $u_{n+1}$ et $v_{n+1}$ existent bien.\\
De plus, $u_n^2>0$, $v_n^2>0$ et $u_n+v_n>0$ donc $u_{n+1}>0$ et $v_{n+1}>0$. La propriété reste vraie au rang $n+1$.\\
On peut donc affirmer, d'après le principe de récurrence, que
\ccl{\forall n\in\N,~u_n\text{ et } v_n\text{ existent bien et } u_n>0,~v_n>0.}
\item \begin{verbatim}
n = input("Entrez n:")
a = input("Entrez a:")
b = input("Entrez b:")
u = a
v = b
for i=1:n
    x=u^2/(u+v)
    v=v^2/(u+v)
    u=x
end
disp(u,"un=")
disp(v,"vn=")
\end{verbatim}
\item \begin{enumerate}
\item Montrons par récurrence sur $n$ que, pour tout $n\in\N$, $\ds x_n=\left(\frac ab\right)^{2^n}$.\\
Tout d'abord, $\ds x_0=\frac{u_0}{v_0}=\frac ab$ et $\ds \left(\frac ab\right)^{2^0}=\left(\frac ab\right)^1=\frac ab$ donc l'égalité est vérifiée pour $n=0$.\\
Soit $n\in\N$, supposons que $\ds x_n=\left(\frac ab\right)^{2^n}$, alors
$$x_{n+1}=\frac{u_{n+1}}{v_{n+1}}=\frac{\frac{u_n^2}{u_n+v_n}}{\frac{v_n^2}{u_n+v_n}}=\frac{u_n^2}{v_n^2}=\left(\frac{u_n}{v_n}\right)^2=x_n^2=\left(\left(\frac ab\right)^{2^n}\right)^2=\left(\frac ab\right)^{2^n\times 2}=\left(\frac ab\right)^{2^{n+1}}$$
donc l'égalité reste vraie au rang $n+1$.\\
On peut donc affirmer, d'après le principe de récurrence, que
\ccl{\forall n\in\N,~x_n=\left(\frac ab\right)^{2^n}.}
\item Pour tout $n\in\N$,
$$y_{n+1}=u_{n+1}-v_{n+1}=\frac{u_n^2}{u_n+v_n}-\frac{v_n^2}{u_n+v_n}=\frac{u_n^2-v_n^2}{u_n+v_n}=\frac{(u_n+v_n)(u_n-v_n)}{u_n+v_n}=u_n-v_n=y_n.$$
Pour tout $n\in\N$, $y_{n+1}=y_n$ donc
\ccl{(y_n)_{n\in\N}\text{ est constante.}}
\end{enumerate}
\item Pour tout $n\in\N$, $v_n>0$ donc $u_n+v_n>u_n>0$ et
$$\frac{u_n^2}{u_n+v_n}<\frac{u_n^2}{u_n}=u_n$$
autrement dit $u_{n+1}<u_n$.
\ccl{(u_n)_{n\in\N}\text{ est strictement décroissante.}}
\item \begin{enumerate}
\item $$\frac{v_k}{v_{k+1}}=\frac{v_k}{\frac{v_k^2}{u_k+v_k}}=\frac{u_k+v_k}{v_k}=\frac{u_k}{v_k}+1=x_k+1=\left(\frac ab\right)^{2^k}+1=1+x^{2^k}.$$
\ccl{\forall k\in\N,~\frac{v_k}{v_{k+1}}=1+x^{2^k}.}
\item On a, d'après (4)(a)(i), pour tout $n\in\N$,
$$P_n=\prod_{k=0}^n\frac{v_k}{v_{k+1}}=\frac{v_0}{v_{n+1}}=\frac1{v_{n+1}}.$$
\ccl{\forall n\in\N,~P_n=\frac1{v_{n+1}}.}
\end{enumerate}
\end{enumerate}

\newcommand{\lb}{\llbracket}
\newcommand{\rb}{\rrbracket}


\section*{\textsc{Probléme } - \'Evolution des intentions de vote}


Dans une élection à venir, deux candidats $A$ et $B$ se présentent. Un groupe d'électeurs est composé de $m$ individus, avec $m\geq 2$. 

Initialement, au jour appelé << jour~$0$ >>, le nombre d'individus préférant le candidat $A$ vaut $a$ (il y en a donc $m-a$ préférant le candidat $B$).
Ensuite, chaque jour, un des individus au hasard dans le groupe en rencontre un autre, au hasard également, et il lui parle des élections. Si leurs intentions de vote différent, il le convainc de voter comme lui.

\medskip

Pour tout entier naturel $n$, on note $X_{n}$ le nombre d'individus du groupe ayant l'intention de voter pour le candidat $A$ le soir du $n$-ième jour. Ainsi, $X_{n}$ est une variable aléatoire à valeurs dans $\lb 0,m\rb$.

On remarque que $X_{0}$ est une variable aléatoire certaine : $P(X_{0}=a)=1$.




\subsection*{Partie I -\  Un cas particulier : $m=4$}


Dans cette partie, on étudie le cas d'un groupe formé de quatre électeurs. 



\begin{enumerate}
\item Soit $i$ et $j$ deux entiers dans $\lb 0,4\rb$. On note $p_{i,j}$ la probabilité pour qu'il y ait exactement $j$ personnes dans le groupe ayant l'intention de voter pour $A$ un jour donné, sachant qu'il y en avait $i$ la veille.


\begin{enumerate}
\item Si aucune personnes ne veut voter pour $A$ les deux personnes se rencontrant veulent toutes les deux voter pour B et il n'y a pas de changement. D'où
\begin{center}
\fbox{$ p_{0,0} = P_{(X_k=0)}(X_{k+1} = 0) = 1$.}
\end{center}
De même si toutes les personnes veulent voter pour A, les deux qui se rencontrent veulent voter pour A et il n'y a aucun changement, et
\begin{center}
\fbox{$ p_{4,4} = P_{(X_k=4)}(X_{k+1} = 4) = 1$.}
\end{center}
\item Chaque jour une personne au maximum change d'avis donc si $X_k = i$, alors le lendemain
$$ i - 1 \leq X_{k+1} \leq i + 1 $$
et si $|i - j| > 2$ cette condition n'est pas vérifiée donc
\begin{center}
\fbox{$p_{i,j} = 0$.}
\end{center}
\item Si $X_k = 1$, on a : \\
Pour avoir $X_{k+1} = 0$, il faut que la première personne tirée  vote pour B ; or il y en a 3 sur les 4 donc la probabilité est de $\frac34$.

Il faut de plus que la deuxième personne tirée vote pour A ; or il y en a 1 sur les 3 restantes donc la probabilité est de $\frac13$.
On obtient donc
\begin{center}
 \fbox{$p_{1,0} = \dfrac{3}{4}\times \dfrac{1}{3} = \dfrac{1}{4}.$}
 \end{center} 
Pour avoir $X_{k+1} = 2$, il faut que la première personne tirée  vote pour A ; or il y en a 1 sur les 4 donc la probabilité est de $\frac14$.

Il faut de plus que la deuxième personne tirée vote pour B ; or il y en a 3 sur les 3 restantes donc la probabilité est de $1$.
On obtient donc
\begin{center}
 \fbox{$p_{1,2} = \dfrac{1}{4}\times 1 = \dfrac{1}{4}.$}
 \end{center} 
 
Enfin, comme $(X_k =i)_{0 \leq i \leq 4}$ est un système complet d'évènements et $p_{1,3} = p_{1,4} = 0$ par la question précédente, on a :

\begin{center}
\fbox{$p_{1,1} = 1 - p_{1,0} - p_{1,2} - p_{1,3} - p_{1,4} = \dfrac{1}{2}$.}
\end{center}

\item Les justifications sont les mêmes que pour la question précédente 



\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=stealth,x=2.5cm,y=4.0cm]

\node[draw,diamond,aspect=1] (Z0) at (0,0) {0};

\node[draw,diamond,aspect=1] (Z1) at (1,0) {1};
\node[draw,diamond,aspect=1] (Z2) at (2,0) {2};
\node[draw,diamond,aspect=1] (Z3) at (3,0) {3};
\node[draw,diamond,aspect=1] (Z4) at (4,0) {4};
\draw[->] (Z0) to[out=25, in=155] (Z1);
\draw[->] (Z1) to[out=25, in=155] (Z2);
\draw[->] (Z2) to[out=25, in=155] (Z3);
\draw[->] (Z3) to[out=25, in=155] (Z4);
\draw[->] (Z4) to[out=-155, in=-25] (Z3);
\draw[->] (Z3) to[out=-155, in=-25] (Z2);
\draw[->] (Z2) to[out=-155, in=-25] (Z1);
\draw[->] (Z1) to[out=-155, in=-25] (Z0);

\draw[->] (Z1) to[out=-55,in=-125,loop] (Z1);
\draw[->] (Z2) to[out=-55,in=-125,loop] (Z2);
\draw[->] (Z3) to[out=-55,in=-125,loop] (Z3);
\draw[->] (Z0) to[out=-145, in=145,loop] (Z0);
\draw[->] (Z4) to[out=35, in=-35,loop] (Z4);
\draw (1,-0.35) node{\small $1/2$};
\draw (1.5,0.17) node{\small $1/4$};
\draw (0.5,0.17) node{\small \color{red} $0$};
\draw (0.5,-0.17) node{\small $1/4$};
\draw (-0.52,0) node{\small $1 $};
\draw (4.52,0) node{\small $1 $};
\draw (1.5,-0.17) node{\small \color{red} $1/3$};
\draw (2,-0.35) node{\small \color{red} $1/3$};
\draw (2.5,-0.17) node{\small \color{red} $1/4$};
\draw (2.5,0.17) node{\small \color{red} $1/3$};
\draw (3,-0.35) node{\small \color{red} $1/2$};
\draw (3.5,-0.17) node{\small \color{red} $0$};
\draw (3.5,0.17) node{\small \color{red} $1/4$};


\end{tikzpicture}
\end{center}


\end{enumerate}

\item On définit la matrice { $M=\begin{pmatrix}
1/2& 1/3&0\\
1/4& {1}/{3}& {1}/{4}\\
0&{1}/{3}& {1}/{2}
\end{pmatrix}$}, et pour tout entier naturel $n$, la matrice colonne~$U_{n}=\begin{pmatrix}
P(X_{n}=1)\\
P(X_{n}=2)\\
P(X_{n}=3)\\
\end{pmatrix}$.

Avec le système complet d'évènement $(X_n = i)_{0  \leq i \leq 4}$, la formule des probabilités totales donne:
\begin{align*}
P(X_{n+1} = 1) & = \sum_{i=0}^4 P(X_n=i) P_{(X_n =i)}(X_{n+1}=1) \\
& = 0 + p_{1,1} P(X_n=1) + p_{2,1} P(X_n = 2) + 0 \\
& \boxed{= \dfrac{1}{2} P(X_n=1) + \dfrac{1}{3}P(X_n = 2)}
\end{align*}

De même on a 
\begin{align*}
P(X_{n+1} = 2) & = \sum_{i=0}^4 P(X_n=i) P_{(X_n =i)}(X_{n+1}=2) \\
& = 0 + p_{1,2} P(X_n=1) + p_{2,2} P(X_n = 2) + p_{3,2} P(X_n = 3) + 0 \\
& \boxed{= \dfrac{1}{4} P(X_n=1) + \dfrac{1}{3}P(X_n = 2)+ \dfrac{1}{4}P(X_n = 3)}
\end{align*}

\begin{align*}
P(X_{n+1} = 3) & = \sum_{i=0}^4 P(X_n=i) P_{(X_n =i)}(X_{n+1}=3) \\
& = 0 + p_{2,3} P(X_n = 2) + p_{3,3} P(X_n = 3) + 0 \\
& \boxed{= \dfrac{1}{3}P(X_n = 2)+ \dfrac{1}{2}P(X_n = 3)}
\end{align*}

Le produit $Mu_n$ donne alors :
\begin{center}
\fbox{$
MU_n = \begin{pmatrix}
\dfrac{1}{2} P(X_n=1) + \dfrac{1}{3}P(X_n = 2) \\
\dfrac{1}{4} P(X_n=1) + \dfrac{1}{3}P(X_n = 2)+ \dfrac{1}{4}P(X_n = 3) \\
\dfrac{1}{3}P(X_n = 2)+ \dfrac{1}{2}P(X_n = 3)
\end{pmatrix} = \begin{pmatrix}
P(X_{n+1} = 1) \\
P(X_{n+1} = 2) \\
P(X_{n+1} = 3) 
\end{pmatrix} = U_{n+1}
$}
\end{center}

On démontre l'égalité  $U_{n}=M^{n}U_{0}$ par récurrence sur $n$.

\renewcommand\labelitemi{\textbullet}
\begin{itemize}
\item {\bf Initialisation :} On a $M^0 = I_2$ et $M^0 U_0 = U_0$ donc l'initialisation est vérifié.
\item {\bf Hérédité :} On suppose que la proposition $\P_n$ est vraie pour un certain rang $n \geq 0$. On a alors
\begin{align*}
U_{n+1} & = M \times U_n \\
& =M \times M^n U_0 \\
& = M^{n+1} U_0
\end{align*}
Donc la proposition $\P_{n+1}$ est vraie. La suite de proposition $(\P_n)$ est héréditaire.
\item {\bf Conclusion :} \fbox{Pour tout $n \in \N$, $U_n = M^n U_0$}.
\end{itemize}
\end{enumerate}



\subsection*{Partie II -\  Le cas général}


On revient dans cette partie au cas général d'un groupe de $m$ électeurs.
	
On note $\pi_{n,k}=P(X_{n}=k)$, la probabilité pour qu'il y ait exactement $k$ électeurs envisageant de voter pour $A$ à l'issue du $n$-iéme jour.


\begin{enumerate}
\item Soit $n$ un entier naturel.

\begin{enumerate}
\item Soit $k\in\lb 0,m-1\rb$. Sachant que $X_n = k$, pour avoir $X_{n+1} = k + 1$ il faut que l'un des k électeurs voulant voter pour A soit tiré en premier (probabilité $\frac{k}{m}$ ) puis que dans les $m -1$ restants, on choisisse un des $m - k$ voulant voter pour B (probabilité $\frac{m-k}{m-1}$) donc
\begin{center}
\fbox{$\ds P_{(X_{n}=k)}(X_{n+1}=k+1)= \frac{k}{m} \times \frac{m-k}{m-1} = \frac{k(m-k)}{m(m-1)}\ ;$}
\end{center}

Sachant que $X_n = k$, pour avoir $X_{n+1} = k - 1$ il faut que l'un des $m-k$ électeurs voulant voter pour B soit tiré en premier (probabilité $\frac{m-k}{m}$ ) puis que dans les $m -1$ restants, on choisisse un des $k$ voulant voter pour A (probabilité $\frac{k}{m-1}$) donc
\begin{center}
\fbox{$P_{(X_{n}=k)}(X_{n+1}=k-1)=\frac{m-k}{m} \times \frac{k}{m-1} = \frac{k(m-k)}{m(m-1)}\ ;$}

Enfin, on remarque que sachant $X_n= k$, $X_{n+1}$ est compris entre $k-1$ et $k+1$ donc 
$$
P_{X_n= k}(X_{n+1}= k-1) + P_{X_n= k}(X_{n+1}= k) + P_{X_n= k}(X_{n+1}= k+1) = 1
$$
donc on obtient
\end{center}
\begin{center}
\fbox{$P_{(X_{n}=k)}(X_{n+1}=k)=1-\frac{2k(m-k)}{m(m-1)} .$}
\end{center}



\item On calcule $\pi_{n+1,k} = P(X_{n+1} = k)$ pour $k \in \entier{1,m-1}$. Avec le système complet d'évènement $(X_n = j)_{j \in \entier{0,m}}$ et en appliquant la formule des probabilités totales, on a 

\begin{align*}
\pi_{n+1,k} & = \sum_{j=0}^n P(X_n = j) P_{(X_n = j)}(X_{n+1} = k) \\
& =  \sum_{j=0}^n \pi_{n,j} P_{(X_n = j)}(X_{n+1} = k) \\
& =  \sum_{j=0}^{k-2} \pi_{n,j} \times 0 +  \sum_{j=k-1}^{k+1} \pi_{n,j} P_{(X_n = j)}(X_{n+1} = k) +  \sum_{j=k+2}^n \pi_{n,j} \times 0 \\
& = \sum_{j=k-1}^{k+1} \pi_{n,j} P_{(X_n = j)}(X_{n+1} = k) \\
& = \pi_{n,k-1} \times \dfrac{(k-1)(m-k+1)}{m(m-1)} + \pi_{n,k} \times \left( 1 - 2 \dfrac{k(m-k)}{m(m-1)} \right) + \pi_{n,k+1} \times \dfrac{(k+1)(m-k-1)}{m(m-1)} \\
& \boxed{= \small \frac{(k-1)(m+1-k)\pi_{n,k-1}+[m(m-1)-2k(m-k)]\pi_{n,k}+(k+1)(m-1-k)\pi_{n,k+1}}{m(m-1)}.}
\end{align*}



\end{enumerate}


\item \begin{enumerate}
\item On montre par récurrence sur $n$ les propositions 
$$
\P_n : \left\{ \forall k\in\lb 1,m-1\rb,\pi_{n,k}\leq \left(\frac{m(m-1)-2}{m(m-1)}\right)^{n} \right\}
$$

\renewcommand\labelitemi{\textbullet}
\begin{itemize}
\item {\bf Initialisation :} $\pi_{0,k}$ est une probabilité donc 
$$
\pi_{0,k} \leq 1 \quad \text{et} \quad \left(\frac{m(m-1)-2}{m(m-1)}\right)^{0} = 1.
$$
L'initialisation est bien vérifié.
\item {\bf Hérédité :} On suppose qu'il existe $n \in \N$ fixé tel que $\forall k \in \entier{1; m?1}$, $\pi_{n,k}\leq \left(\frac{m(m-1)-2}{m(m-1)}\right)^{n}$.
Alors pour tout $k \in \entier{1,m-1}$, on a :
$$
\pi_{n+1,k} \leq \small \frac{(k-1)(m+1-k)+[m(m-1)-2k(m-k)]+(k+1)(m-1-k)}{m(m-1)} \times \left( \dfrac{m(m-1)-2}{m(m-1)} \right)^n
$$
On simplifie le numérateur du premier facteur qu'on note $N$ :
\begin{align*}
N & = (k-1)(m+1-k)+[m(m-1)-2k(m-k)]+(k+1)(m-1-k) \\
& = k(m - k) + k - m - 1 + k + m(m - 1) - 2k(m - k) + k(m - k) - k + m - 1 - k \\
& =  k(m - k) [1 - 2 + 1] + k(1 + 1 - 1 - 1) + m(-1 + 1) + m(m - 1) - 2 \\
& = m(m-1) - 2
\end{align*}
ce qui donne enfin :
\begin{align*}
\pi_{n+1,k} & \leq \dfrac{m(m-1) - 2}{m(m-1)} \times \left( \dfrac{m(m-1)-2}{m(m-1)} \right)^n \\
 & \leq \left( \dfrac{m(m-1)-2}{m(m-1)} \right)^{n+1}
\end{align*}
La propriété est vraie au rang n + 1.
\item {\bf Conclusion :} Pour tout $n \in \N$ et pour tout $k \in \entier{1;m-1}$ 
\begin{center}
\fbox{$\pi_{n,k} \leq  \left( \dfrac{m(m-1)-2}{m(m-1)} \right)^n$.}
\end{center}
\end{itemize}

\end{enumerate}

\item Pour tout entier naturel $n$, on pose $Z_{n}=X_{n+1}-X_{n}$.

\begin{enumerate}
\item Comme une seule personne peut changer d'avis chaque jour, on a
$$
|X_{n+1} - X_n| \leq 1
$$
donc $Z_n(\Omega) \subset \{-1 ; 0 ; 1\}$. \\

De plus, avec $X_n = 1$ qui peut donner avec une probabilité non nulle $X_{n+1} = 0$, $X_{n+1} = 1$ et $X_{n+1} = 2$ on a bien 
$\{-1 ; 0 ; 1\} \subset Z_n(\Omega)$ et enfin
\begin{center}
\fbox{ $Z_n(\Omega) = \{-1 ; 0 ; 1\}$.}
\end{center}
\item Avec le système complet d'évènement $(X_n = k)_{k \in \entier{0;m}}$ on a :
\begin{align*}
P(Z_{n}=1) & = \sum_{k=0}^m P \left( (Z_n=1) \cap (X_n = k) \right) \\
& =  \sum_{k=0}^m P \left( (X_{n+1} - X_n =1) \cap (X_n = k) \right) \\
& = \sum_{k=0}^m P \left( (X_{n+1} = k+1) \cap (X_n = k) \right)
\end{align*}
Or $X_{n+1} = m+1$ est impossible et $(X_n =0 )\cap (X_{n+1} = 1)$ également car si $X_n= 0$ alors $X_{n+1} = 0$. 
Enfin, en utilisant la formule des probabilités composées et avec le résultat du $1(a)$, on a
\begin{align*}
P(Z_n = 1) & = \sum_{k=1}^{m-1} P(X_n = k) P_{(X_n = k)}(X_{n+1}= k+1) \\
& \boxed{= \sum_{k=1}^{m-1} \pi_{n,k} \times \dfrac{k(m-k)}{m(m-1)}}
\end{align*} 
\item Un raisonnement identique donne (avec $(X_{n+1} = ?1)$ et $(X_n = m) \cap (X_{n+1} = m - 1)$ impossibles) :
\begin{align*}
P(Z_n = -1) & = \sum_{k=1}^{m-1} P(X_n = k) P_{(X_n = k)}(X_{n+1}= k-1) \\
& = \sum_{k=1}^{m-1} \pi_{n,k} \times \dfrac{k(m-k)}{m(m-1)} \\
& \boxed{ = P(Z_n = 1)}
\end{align*} 
\item On en déduit que 
\begin{align*}
E(Z_n) & = -1 \times P(Z_n = -1) + 0 \times P(Z_n = 0) + 1 \times P(Z_n = 1) \\
& = -P(Z_n=1) + P(Z_n = 1) \\
& \boxed{= 0}
\end{align*}
\item Pour tout $n \in \N$, par linéarité de l'espérance
$$ 
E(Z_n) = E(X_{n+1}) - E(X_n) = 0
$$
donc $E(X_{n+1}) = E(X_n)$. 
On montre alors par récurrence que pour tout $n \in \N$, 
$$
E(X_n) = E(X_0) = a
$$
car $X_0$ est une variable aléatoire certaine égale à $a$. 
\begin{center}
\fbox{La suite $(E(X_n))_n$ est bien constante égale à $a$.}
\end{center} 
\end{enumerate}
\end{enumerate}

\end{document}